package com.tlvip.arithmetic.ch07;

/**
 * <p>description：插入排序</p>
 * 假设序列分为两段，一段有序，另一段无序，比如假定升序排列，左端有序，右端无序
 * 1 将左端第一个元素认为是有序，右侧的无序，指针指向第一个元素；
 * 2 从左侧最后一个有序元素的next向右侧逐个遍历，
 *    每遍历右侧一个无序的元素，左如下操作
 *    倒序逐个遍历左侧有序元素，如果存在比右侧的数据大，则比较交换
 *    每倒序遍历完左侧有序序列，左侧指针向右端移动一个位置
 *    每次比较的元素会越来越少
 *
 * <p>copyright： copyright(C)2016-2099</p>
 * <p>Life is short,we need passion</p>
 * <p>Summary： </p>
 * <p>instructions： </p>
 * Date 1/26/21</p>
 * Author mac
 *
 * @version 1.0
 */
public class InsertSort {
    public static void main(String[] args) {
        int a[] = {9, 8, 7, 0, 1, 2, 3};
        int n = a.length;
        print(a);
        int count = 0;
        // 两层循环 时间复杂度O(n^2)
        // 最好的情况：O(n)，数列是顺序的情况下
        // 第一个元素默认有序，跳过，从第二个元素开始遍历
        for (int i = 1; i < n; i++) {
            // 数组的前面一端是排好序的，后面一段未知顺序，从后向前遍历，不用大量移动元素，
            // 反之则可能会移动元素，所以使用倒序
            for (int j = i; j > 0; j--) {
                count++;
                if (a[j] < a[j - 1]) {
                    int temp = a[j];
                    a[j] = a[j - 1];
                    a[j - 1] = temp;
                } else {
                    // 如果 a[j] >= a[j-1]，则不用向前比较
                    // 因为 a[j-1]是左侧最大的元素，没有继续向前比较的需要了
                    break;
                }
            }
            print(a);
        }
        System.out.println("总共执行:" + count + "次");
    }

    public static void print(int a[]) {
        System.out.println("===");
        for (int i : a) {
            System.out.print(i + "  ");
        }
        System.out.println();
    }
}
